package project2;

public class exact_5 {

    private int[][][][] S;
    private int[][] score_matrix;
    private int k, n, gap_cost;
    private String[] seq;

    exact_5(int[][] m, int g, String[] s, int i, int j) {
        score_matrix = m;
        gap_cost = g;
        seq = s;
        k = i;
        n = j;
    }

    public void get_optimal_cost() {

        double time = System.nanoTime();

        String[] binary = new String[(int) java.lang.Math.pow(2,k)-1];
        for(int i=0; i<java.lang.Math.pow(2,k)-1; i++) {
            binary[i] = Integer.toBinaryString(i+1);
            for(int j=binary[i].length(); j<k; j++)
                    binary[i] = (new String("0")).concat(binary[i]);
        }

        S = new int[n+1][n+1][n+1][n+1];
        int[][][][] aux = new int[n+1][n+1][n+1][n+1];

        for(int j=0; j<=n; j++) {
            for(int i1=0; i1<=n; i1++)
                for(int i2=0; i2<=n; i2++)
                    for(int i3=0; i3<=n; i3++)
                        for(int i4=0; i4<=n; i4++) {
                            S[i1][i2][i3][i4] = 5000;
                            //for all precedors
                            for(int p=0; p<java.lang.Math.pow(2,k)-1; p++) {
                                int[] a = new int[5];
                                a[0] = i1 - Character.digit(binary[p].charAt(0),10);
                                a[1] = i2 - Character.digit(binary[p].charAt(1),10);
                                a[2] = i3 - Character.digit(binary[p].charAt(2),10);
                                a[3] = i4 - Character.digit(binary[p].charAt(3),10);
                                a[4] = j - Character.digit(binary[p].charAt(4),10);
                                if(a[0]>=0&&a[1]>=0&&a[2]>=0&&a[3]>=0&&a[4]>=0){
                                    int val = 0;
                                    if(j>0)
                                        val = aux[a[0]][a[1]][a[2]][a[3]];
                                    else
                                        val = S[a[0]][a[1]][a[2]][a[3]];
                                    for(int l1=0; l1<k-1; l1++)
                                        for(int l2=l1+1; l2<k; l2++) {
                                            //compare seq l1 and l2 - at the right positions
                                            if(!(binary[p].charAt(l1)==0&&binary[p].charAt(l2)==0))
                                                if(binary[p].charAt(l1)==1&&binary[p].charAt(l2)==1)
                                                    val += score_matrix[value(seq[l1].charAt(a[l1]))][value(seq[l2].charAt(a[l2]))];
                                                else
                                                    val += gap_cost;
                                        }
                                    if(val<S[i1][i2][i3][i4])
                                        S[i1][i2][i3][i4] = val;
                                }

                            }
                        }
            for(int i1=0; i1<=n; i1++)
                for(int i2=0; i2<=n; i2++)
                    for(int i3=0; i3<=n; i3++)
                        for(int i4=0; i4<=n; i4++)
                            aux[i1][i2][i3][i4] = S[i1][i2][i3][i4];
        }

        double end_time = (System.nanoTime()-time)/1000000000;

        System.out.println("Running time in s: "+end_time);
        System.out.println("Optimal cost: "+S[n][n][n][n]);
    }

     private int value(char c){
        if(c=='a') return 0;
        if(c=='c') return 1;
        if(c=='g') return 2;
        if(c=='t') return 3;
        return -1;
    }

}
